#include<iostream>
#include<vector>
using namespace std;
/*
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。 
解题思路：
该题目是完全背包问题，每个物品能够允许被重复使用，背包容量为amount
dp[j]的含义装满容量为j的背包最多有dp[j]种方法
且当背包中已经有重量为1的物品时，装满背包的最多方法为dp[j-nums[1]]
当背包中已经有重量为2的物品时，装满背包的最多方法为dp[j-nums[2]]
以此类推，dp[j]+=dp[j-nums[i]]
*/
int dp(vector<int> nums,int amount)
{
    //创建dp数组
    vector<int> dp(amount+1);
    dp[0]=1;
    //遍历dp数组,求数的组合时先遍历物品再遍历背包,求数的排列时先遍历背包再遍历物品
    for(int i=0;i<nums.size();i++)
    {
        //完全背包问题与0-1背包问题的区别在于完全背包问题再遍历背包容量时是从前往后遍历
        for(int j=nums[i];j<=amount;j++)
        {
            dp[j]+=dp[j-nums[i]];
        }
    }
    return dp[amount];  
}
int main()
{
    cout<<"enetr amount:"<<endl;
    int amount;
    cin>>amount;
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter nums:"<<endl;
    vector<int> nums(number);
    for(int i=0;i<number;i++)
        cin>>nums[i];
    cout<<dp(nums,amount);
    return 0;
}